#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,Z[2001000],cnt1[30],cnt2[30],sum[30],CN,BN,nown,sumn,nown2;
ll res;
char s[2001000];
int main(){
//	freopen("string.in","r",stdin);
//	freopen("string.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%s",s),n=strlen(s),memset(sum,0,sizeof(sum)),memset(cnt1,0,sizeof(cnt1)),memset(cnt2,0,sizeof(cnt2)),res=CN=BN=0;
		for(int i=0;i<n;i++)cnt1[s[i]-'a']^=1;
		for(int i=0;i<26;i++)CN+=cnt1[i];
		int Centre=-1,Rpos=-1;
		for(int i=1;i<n;i++){
			if(i<=Rpos)Z[i]=min(Z[i-Centre],Rpos-i+1);
			else Z[i]=0;
			while(i+Z[i]<n&&s[Z[i]]==s[i+Z[i]])Z[i]++;
			if(i+Z[i]>Rpos)Centre=i,Rpos=i+Z[i]-1;
		}
//		for(int i=1;i<n;i++)printf("%d ",Z[i]);puts("");
		nown=CN,nown2=sumn=0;
		for(int i=1;i<n;i++){
			if(cnt1[s[i-1]-'a'])sumn-=sum[nown--];
			else sumn+=sum[++nown];
			cnt1[s[i-1]-'a']^=1;
			int tot=min(Z[i],n-i-1)/i+1;
			int N1=(tot+1)>>1,N2=(tot)>>1;
//			printf("%d:%d %d\n",tot,N1,N2);
			res+=1ll*sumn*N1;
			if(cnt2[s[i-1]-'a'])nown2--;
			else nown2++;
			cnt2[s[i-1]-'a']^=1;
			sum[nown2]++;
			if(nown2<=nown)sumn++;
			res+=1ll*BN*N2;
			if(nown2<=CN)BN++;
		}
		printf("%lld\n",res);
	}
	return 0;
}
